package com.LeeCode;

/**
 * 有序矩阵中第 K 小的元素
 */

public class Code378 {
    public static void main(String[] args) {
        int[][] matrix = {
                {1, 5, 9},
                {10, 11, 13},
                {12, 13, 15}
        };
        int k = 2;
        System.out.println(new Code378().kthSmallest(matrix, k));

    }

    public int kthSmallest(int[][] matrix, int k) {
        int n = matrix.length;
        int left = matrix[0][0] - 1, right = matrix[n - 1][n - 1];
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            int count = 0;
            for (int i = 0; i < n; i++) {
                if (matrix[i][0] > mid) break;
                count += lowerBound(matrix[i], mid) + 1;
            }
            if (count >= k)
                right = mid;
            else
                left = mid;
        }
        return right;
    }

    private int lowerBound(int[] nums, int target) {
        int left = 0, right = nums.length;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] <= target) {
                left = mid;
            } else
                right = mid;
        }
        return left;
    }
}
